"""P15 15.基础提升 大数据题目的解题技巧、位运算相关知识点"""

"""
大数据题目的解题技巧：
1)哈希函数可以把数据按照种类均匀分流
2)布隆过滤器用于集合的建立与查询，并可以节省大量空间
3)一致性哈希解决数据服务器的负载管理问题
4)利用并查集结构做岛问题的并行计算
5)位图解决某一范围上数字的出现情况，并可以节省大量空间
6)利用分段统计思想、并进一步节省大量空间
7)利用堆、外排序来做多个处理单元的结果合并
"""

"""
有一个包含100亿个URL的大文件，假设每个URL占用64B,请找出其中所有重复的URL
【补充】
某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设汁一种求出每天热门Top100
词汇的可行办法

原问题设计思路：
可以用布隆过滤器实现
补充部分的思路：
将海量的词汇通过哈希函数分为多个小文件，每个小文件根据词频
创建各自的大根堆，然后取所有小文件的大根堆的堆顶组成一个总的大根堆，获取Top100
词汇时在总的大根堆弹出堆顶，然后将弹出元素所在的小文件的堆顶也弹出，再将小文件
新的堆顶加入到总的大根堆
"""

"""
32位无符号整数的范围是0 ~ 4294967295，现在有40亿个无符号整数，可以使用最多1GB的
内存，找出所有出现了两次的数。
【补充】
可以使用最多10MB的内存，怎么找到这40亿个整数的中位数？

原问题设计思路：
1、通过哈希函数将40亿个无符号整数分流为多个小文件，再对每个小文件去求解
2、用两个bit位来记录一个整数出现次数的情况，通过位图来解决
补充部分的思路：
将整数范围等分为多个范围，统计各个小范围的词频数，然后从小到大累加词频数，
直到累加和大于或者等于目标值（第一次时为20亿，后面根据情况相减算出对应范围
的目标值），从而确认中位数所在的小范围，后面按照同样的思路缩小范围，直到找到中位数
"""

"""
10G的文件，里面是无序排列的有符号整数，使用最多5G的内存，
输出一个内容为有序整数的文件

设计思路1：
将有符号整数的范围根据小根堆（比较整数的值，也携带该整数的词频）和内存限制
分成许多的小范围。小范围从小到大依次开始，每次遍历原文件的整数，如果当前整数
在当前小范围内，就加入到小根堆，遍历完原文件的整数后，将小根堆的整数按从小到大
的顺序并结合词频输出到另一个文件中，再去处理下一个小范围

设计思路2：
根据内存限制设计一个合适大小的大根堆（比较整数的值，也携带该整数的词频）。
遍历文件的整数，如果大根堆有空间放入，就将整数放入大根堆，
在大根堆空间不足的情况下，如果整数大于大根堆的堆顶整数，
则跳过不放入；如果整数小于大根堆的堆顶整数，则堆顶整数弹出，再放入。
遍历完一遍原文件，就将大根堆的整数输出到另一个文件中，
然后重新遍历原文件，直到原文件中所有整数都处理过
"""


"""
位运算的题目,给定两个有符号32位整数a和b,返回a和b中较大的。要求：不用做任何比较判断。
"""


def flip(n: int) -> int:
    """保证n不是1就是0的情况下：1 -> 0, 0 -> 1"""
    return n ^ 1


def sign(n: int) -> int:
    """n非负数返回1，n为负数返回0"""
    return flip((n >> 31) & 1)


def get_max1(a: int, b: int) -> int:
    """返回a和b中较大的"""
    sign_a = sign(a - b)  # a - b可能会溢出
    sign_b = flip(sign_a)
    return a * sign_a + b * sign_b


def get_max2(a: int, b: int) -> int:
    """返回a和b中较大的"""
    sign_a = sign(a)
    sign_b = sign(b)
    # a、b差值情况
    sign_c = sign(a - b)
    # a、b符号情况
    sign_diff = sign_a ^ sign_b
    sign_same = flip(sign_diff)
    # 返回a的情况：1、a和b符号不同且a>0；2、a和b符号相同且a-b>=0
    return_a = sign_diff * sign_a + sign_same * sign_c
    return_b = flip(return_a)
    return a * return_a + b * return_b


"""将if和else的判断转换为加号两边的形式，只有加号两边为互斥的条件"""


"""
判断一个32位正数是不是2的幂、4的幂

判断是否为2的冥：
1)如果一个数是2的冥，那么该数的二进制表示中只有一个位是1
2)如果一个数X是2的冥，那么X & (X - 1) = 0

判断是否为4的冥：
如果一个数X是4的冥，那么它也是2的冥，通过前面判断先验证是2的冥，
然后如果 X & 0101……01 != 0，那么数X就是4的冥
"""


def is_2_power(n: int) -> bool:
    """判断一个32位正数是不是2的幂"""
    return (n & (n - 1)) == 0


def is_4_power(n: int) -> bool:
    """判断一个32位正数是不是4的幂"""
    return (n & (n - 1)) == 0 and (n & 0x55555555) != 0


"""
给定两个有符号32位整数a和b,不能使用算术运算符，分别实现a和b的加、减、乘、除运
算
【要求】
如果给定a、b执行加减乘除的运算结果就会导致数据的溢出，那么你实现的函数不必对此
负责，除此之外请保证计算过程不发生溢出
"""

"""
加法：
a ^ b：表示a和b无进位相加的结果A
(a & b) << 1：表示a和b相加的进位结果B
将a+b转换为A+B的形式，直到B为0，则此时的A=a+b
"""


def addition(a: int, b: int) -> int:
    """a + b"""
    result = a
    while b:
        result = a ^ b
        b = (a & b) << 1
        a = result
    return result


"""
减法：
a减b，等于a加上b的相反数
~b + 1：表示b的相反数
"""


def subtraction(a: int, b: int) -> int:
    """a - b"""
    return addition(a, addition(~b, 1))


"""乘法：模拟手算的过程"""


def multiplication(a: int, b: int) -> int:
    """a * b"""
    result = 0
    while b:
        if b & 1:
            result = addition(result, a)
        a = a << 1
        b = b >> 1
    return result


"""
除法：
对于a // b，将b左移得到c，但c不大于a，在结果中的同样左移位置上为1
将a - c的结果当作新的b，重复上面步骤，直到a - c = 0
"""


def division(a: int, b: int) -> int:
    """a // b"""
    x = ~a + 1 if a < 0 else a
    y = ~b + 1 if b < 0 else b
    result = 0
    i = 31
    while i > -1:
        if (x >> i) >= y:
            result = result | (1 << i)
            x = subtraction(x, y << 1)
        i = subtraction(i, 1)
    return ~result + 1 if a < 0 and b < 0 else result
